package com.fr.sort;
/**  
 *  
 * @author furong   
 * @version 创建时间：2016年5月10日 下午4:01:55  
 */
public class HeapSort extends ShowSort{
	public static void buildHead(int [] a){
		int n = a.length;
		for (int i = (n - 1) / 2; i >= 0; i --){
			heapAdjust(a, i, n);
		}
		showHeap(a);
	}

	private static void heapAdjust(int[] a, int s, int length) {
		 int tmp  = a[s];  
		    int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
		    while (child < length) {  
		        if(child+1 <length && a[child]<a[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
		            ++child ;  
		        }  
		        if(a[s]<a[child]) {  // 如果较大的子结点大于父结点  
		            a[s] = a[child]; // 那么把较大的子结点往上移动，替换它的父结点  
		            s = child;       // 重新设置s ,即待调整的下一个结点的位置  
		            child = 2*s+1;  
		        }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
		             break;  
		        }  
		        a[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
		    }  
	}
	private static void showHeap(int a[]){
		int n = a.length;
		int sum = 0;
		a:for(int i =0; i < n; i++){
			int k = (int) Math.pow(2, i);
			for(int j = 0; j < k; j ++){
				sum ++;
				if (sum > n){
					break a;
				}
				System.out.print(a[sum - 1]);
			}
			System.out.println();
		}
	}
}
